﻿#pragma once
#include <stdio.h>
#include<stdlib.h>

//打印
void PrintArray(int* a, int n)
{
	int i = 0;
	for (i = 0; i < n; i++)
	{
		printf("%d ", a[i]);
	}
	printf("\n");
}

void Swap(int* p1, int* p2)
{
	int tmp = *p1;
	*p1 = *p2;
	*p2 = tmp;
}
//三数取中
int GetMidIndex(int* a, int left, int right)
{
	int mid = (left + right) >> 1;
	if (a[left] < a[mid])
	{
		if (a[mid] < a[right])  //mid在中间

		{
			return mid;
		}
		else if (a[left] > a[right])  //mid最小
		{
			return left;
		}
		else
		{
			return right;
		}
	}
	else
	{
		if (a[mid] > a[right])
		{
			return mid;
		}
		else if (a[right] < a[left])
		{
			return right;
		}
		else
		{
			return left;
		}
	}

}

// 挖坑法
int PartSort2(int* a, int left, int right)
{
	int midIndex = GetMidIndex(a, left, right);
	Swap(&a[left], &a[midIndex]);

	int key = a[left];
	while (left < right)
	{
		// 找小
		while (left < right && a[right] >= key)
		{
			--right;
		}
		// 放到左边的坑位中,右边就形成新的坑
		a[left] = a[right];
		// 找大
		while (left < right && a[left] <= key)
		{
			++left;
		}
		// 放到右边的坑位中，左边就形成新的坑
		a[right] = a[left];
	}
	a[left] = key;
	return left;
}
void QuickSort(int* a, int begin, int end)
{
	if (begin >= end)
		return;
	int keyi = PartSort2(a, begin, end);
	QuickSort(a, begin, keyi - 1);
	QuickSort(a, keyi + 1, end);
}

int main()
{
	int a[] = { 6,1,2,7,9,3,4,5,10,8 };
	int n = sizeof(a) / sizeof(a[0]);
	QuickSort(a, 0, n - 1);
	PrintArray(a, n);
	return 0;
}